# 7
def f(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return f(n - 1) + f(n - 2)
print(f(5))

def f2(n):
    a = [1, 2]
    for i in range(2, n):
        a.append(a[i - 1] + a[i - 2])
    return a
print(f2(5))


def f3(n):
    a,b = 1, 2
    for i in range(2, n):
        a, b = b, a + b
    return b
print(f3(5))

x = 0
def f4(n):
    global x
    if n == 0:
        x += 1
        return 1
    if n < 0:
        return 0
    f4(n-2)
    f4(n-1)

f4(6)
print(x)


# a b c 

# 3
# a -> c 
# a -> b 
# c -> b
# a -> c 
# b -> a
# b -> c 
# a -> c 

# def hanoi(n, a, b, c):
#     if n == 1:
#         print(a, '--->', b)
#         return None
#     else:
#         hanoi(n-1, a, c, b)
#         print(a, '--->', b)
#         hanoi(n-1,b, a, c)

# hanoi(3, 'a', 'b', 'c')

#汉诺塔
def move (n,a,b,c,d=1):
    if n == 1:
        print(a,'-->',c)
        return d

    d=d+move(n-1,a,c,b)  #怎么吧n-1个碟子从，a移到b，
    print(a,'-->',c)

    d=d+move(n-1,b,a,c)  #怎么将n-1个碟子从b移到c去
    return d   #d是实现记录操作步数

print(move(3,'A','B','C'))

